/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package com.factory.server.algorithms;

import com.factory.server.algorithms.Graph.Node;
import com.factory.server.analyser.Analyser;
import java.util.ArrayList;
import java.util.List;
import java.util.logging.Logger;

/**
 *
 * source: http://www.algoritmy.net/article/1381/Topologicke-usporadani
 */
public class TopologicalOrder {

    static final Logger LOG = Logger.getLogger(Analyser.class.getName());
    private static GraphProblemresult graphResut;

    public GraphProblemresult execute(Graph graph) {
        graphResut = new GraphProblemresult();
        orderTopologically(graph);
        return graphResut;
    }

    /**
     * Vypise topologicke usporadani acyklickeho grafu
     *
     * @param graph graf
     */
    public static void orderTopologically(Graph graph) {
        //Stavy jednotlivych uzlu
        List<Integer> roots = new ArrayList<Integer>();
        for (int i = 0; i < graph.getNodes().size(); i++) {
            //pokud nema v puvodnim grafu potomky, tak je korenem 
            //v opacne orientovanem grafu
            if (graph.getNodes().get(i).successors.isEmpty()) {
                roots.add(i);
            }
        }
        Graph inverted = graph.inverse(); //vytvor opacne orientovany graf
        int[] state = new int[inverted.getNodes().size()];

        for (int i = 0; i < state.length; i++) {
            state[i] = 0; //0==FRESH
        }
        for (Integer i : roots) {
            doOrdering(inverted, i, state);
        }
    }

    /**
     * Provadi samotne usporadani grafu
     *
     * @param graph graf
     * @param vertexNr cislo aktualniho uzlu
     * @param state pole stavu
     */
    private static void doOrdering(Graph graph, int vertexNr, int[] state) {
        state[vertexNr] = 1; //OPENED==1
//        for (Integer i = 0; i < graph.getNodes().get(vertexNr).getSuccessors().size(); i++) {
        for (Node succ: graph.getNodes().get(vertexNr).getSuccessors()){
            if (state[succ.identifier] == 0) {
                doOrdering(graph, succ.identifier, state);
            } else if (state[succ.identifier] == 1) {
                throw new IllegalArgumentException("Graf obsahuje cykly");
            }
        }
        graphResut.getNodesList().add(vertexNr);
        state[vertexNr] = -1; //-1==CLOSED
    }
    
}
